﻿#pragma once

#include <learn/check.h>
#include <learn/dll_ext.h>
#include <learn/math/math.h>
#include <learn/math/matrix.h>
#include <learn/stl/list.h>
#include <learn/stl/tree.h>
#include <learn/utils/sfinae.h>

#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>

namespace xi
{

namespace math
{

namespace details
{

template <typename T> struct Graph_Data
{
    enum Color
    {
        Black,
        Gray,
        White
    };

    T data = T{};
    Color color = White;

    friend std::ostream &operator<<(std::ostream &os, const Graph_Data &data)
    {
        os << data.data << ", " << utils::enum_name(data.color);
        return os;
    }
};

} // namespace details

class EXT_SYMBOL Graph_Sparse
{
    using Link_List = std::shared_ptr<stl::List<std::size_t>>;
    using VData = details::Graph_Data<float>;
    using EData = details::Graph_Data<float>;

  protected:
    std::vector<Link_List> m_adjList;
    std::vector<VData> m_vData;
    std::unordered_map<std::tuple<std::size_t, std::size_t>, EData, Hash_Tuple<std::size_t>> m_eData;

  public:
    Graph_Sparse(Graph_Sparse &&) = delete;

    /**
     * @brief 默认构造
     *
     */
    Graph_Sparse(std::size_t n);

    /**
     * @brief 获得图的大小
     *
     * @return std::size_t
     */
    std::size_t size() const;

    /**
     * @brief 创建无向边
     *
     * @param[in] u
     * @param[in] v
     * @param[in] weight
     */
    void create_undirected_edge(std::size_t u, std::size_t v, float weight = 1.0f);

    /**
     * @brief 创建有向边
     *
     * @param[in] u
     * @param[in] v
     * @param[in] weight
     */
    void create_directed_edge(std::size_t u, std::size_t v, float weight = 1.0f);

    /**
     * @brief 创建 u 的多个无向边
     *
     * @param[in] u
     * @param[in] v
     * @param[in] weights
     */
    void create_undirected_edges(std::size_t u, const std::vector<std::size_t> &v, const std::vector<float> &weights);

    /**
     * @brief 创建 u 的多个有向边
     *
     * @param[in] u
     * @param[in] v
     * @param[in] weights
     */
    void create_directed_edges(std::size_t u, const std::vector<std::size_t> &v, const std::vector<float> &weights);

    /**
     * @brief 转置图
     *
     */
    void transpose();

    /**
     * @brief 移除冗余边和自循环边
     *
     */
    void remove_duplicates();

    /**
     * @brief 获得 u 的邻接顶点
     *
     * @param[in] u
     * @return std::vector<std::size_t>
     */
    std::vector<std::size_t> adjacent_vertices(std::size_t u) const;

    /**
     * @brief 判断 u 到 v 是否存在边
     *
     * @param[in] u
     * @param[in] v
     * @return true
     * @return false
     */
    bool adjacent_edge(std::size_t u, std::size_t v) const;

    /**
     * @brief 无权广度优先搜索，以 s 为起点
     *
     * @param[in] s
     * @return std::unique_ptr<MN_Tree<float*>>
     */
    std::unique_ptr<stl::MN_Tree<float *>> bfs(std::size_t s);

    /**
     * @brief 无权深度优先搜索，以 s 为起点
     *
     * @param[in] s
     * @return std::vector<std::tuple<float, float>>
     */
    std::vector<std::tuple<float, float>> dfs(std::size_t s);

    /**
     * @brief 打印图
     *
     * @param[in] os
     * @param[in] graph
     * @return std::ostream&
     */
    friend EXT_SYMBOL std::ostream &operator<<(std::ostream &os, const Graph_Sparse &graph);
};

class EXT_SYMBOL Graph_Dense
{
    using Matrix = Matrix<int>;

  protected:
    Matrix m_adjMat;
    Matrix m_wMat;

  public:
    Graph_Dense(Graph_Dense &&) = delete;

    /**
     * @brief 默认构造
     *
     */
    Graph_Dense(std::size_t n);

    /**
     * @brief 获得图的大小
     *
     * @return std::size_t
     */
    std::size_t size() const;

    /**
     * @brief 创建无向边
     *
     * @param[in] u
     * @param[in] v
     * @param[in] weight
     */
    void create_undirected_edge(std::size_t u, std::size_t v, float weight = 1.0f);

    /**
     * @brief 创建有向边
     *
     * @param[in] u
     * @param[in] v
     * @param[in] weight
     */
    void create_directed_edge(std::size_t u, std::size_t v, float weight = 1.0f);

    /**
     * @brief 创建 u 的多个无向边
     *
     * @param[in] u
     * @param[in] v
     * @param[in] weights
     */
    void create_undirected_edges(std::size_t u, const std::vector<std::size_t> &v, const std::vector<float> &weights);

    /**
     * @brief 创建 u 的多个有向边
     *
     * @param[in] u
     * @param[in] v
     * @param[in] weights
     */
    void create_directed_edges(std::size_t u, const std::vector<std::size_t> &v, const std::vector<float> &weights);

    /**
     * @brief 转置图
     *
     */
    void transpose();

    /**
     * @brief 移除冗余边和自循环边
     *
     */
    void remove_duplicates();

    /**
     * @brief 获得 u 的邻接顶点
     *
     * @param[in] u
     * @return std::vector<std::size_t>
     */
    std::vector<std::size_t> adjacent_vertices(std::size_t u) const;

    /**
     * @brief 判断 u 到 v 是否存在边
     *
     * @param[in] u
     * @param[in] v
     * @return true
     * @return false
     */
    bool adjacent_edge(std::size_t u, std::size_t v) const;

    /**
     * @brief 判断 u 到 v 的最短路径长度，以 len 为上界
     *
     * @param[in] u
     * @param[in] v
     * @param[in] len
     * @return std::size_t
     */
    std::size_t shortest_path(std::size_t u, std::size_t v, std::size_t len);

    /**
     * @brief 打印图
     *
     * @param[in] os
     * @param[in] graph
     * @return std::ostream&
     */
    friend EXT_SYMBOL std::ostream &operator<<(std::ostream &os, const Graph_Dense &graph);
};

} // namespace math

} // namespace xi
